package cn.java.sort;

import java.util.Arrays;

import javax.xml.crypto.Data;

/**
 * 希尔排序 2019-11-03
 * 
 * @author zjb
 *
 */
public class ShellSort {

	/**
	 * 希尔排序： 希尔排序(Shell Sort) 是插入排序的一种，因D.L Shell于1959年提出而得名。
	 * Shell排序的中心思想是将数据进行分组，然后对每一组数据进行排序，在每一组数据都有序之后，就可以对所有的分组利用插入排序进行最后一次排序。
	 * 这样可以显著减少数据交换的次数，以达到加快排序速度的目的。
	 */

	public static void ShellSort(int[] arr, int Index) {
		int i, j, k; // 循环计数变量
		int temp; // 暂存变量
		boolean Change; // 数据是否改变
		int DataLength; // 分割集合的间隔长度
		int pointer; // 进行处理的位置

		DataLength = (int) Index / 2; // 初始集合间隔长度

		while (DataLength != 0) { // 数列仍可进行分割
			// 对各个集合进行处理
			for (j = DataLength; j < Index; j++) {
				Change = false;
				temp = arr[j]; // 暂存Data[j]的值，待交换值时用。
				pointer = j - DataLength; // 进行数据处理的位置

				// 进行集合内数值的比较与交换
				while (temp < arr[pointer] && pointer >= 0 && pointer <= Index) {
					arr[pointer + DataLength] = arr[pointer];
					// 计算下一个欲进行处理的位置
					pointer = pointer - DataLength;
					Change = true;
					if (pointer < 0 || pointer > Index)
						break;
				}

				// 与最后的数值交换
				arr[pointer + DataLength] = temp;

				if (Change) {
					// 打印目前排序的结果
					System.out.print("排序中：");
					for (k = 0; k < Index; k++)
						System.out.printf("%3s", arr[k]);
					System.out.println("");
				}
			}
			DataLength = DataLength / 2; // 计算下次分割的间隔长度
		}

	}

	/**
	 * 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又缩小增量排序，因DL.Shell于1959年提出得名。
	 * 希尔排序实质上是一种分组插入方法。它的基本思想是：对n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序
	 * 元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个数组中；然后，对各组内的元素进行直接插入排序。这一趟排序完成后，
	 * 每一个组的元素多是有序的。然后减少gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列多是有序的。
	 */

	/**
	 * 希尔排序
	 * 
	 * @param arr
	 *            --待排序的数组
	 * @param n
	 *            --数组的长度
	 */
	private static void shellSort(int[] arr, int n) {

		// gap为步长，每次减为原来的一半
		for (int gap = n / 2; gap > 0; gap /= 2) {

			// 工gap个组，对每一个组执行直接插入排序
			for (int i = 0; i < gap; i++) {

				for (int j = i + gap; j < n; j += gap) {
					// 如果arr[j]<arr[j-gap],则寻找arr[j]的位置，并将后面数据的位置后移
					if (arr[j] < arr[j - gap]) {
						int temp = arr[j];
						int k = j - gap;
						while (k >= 0 && arr[k] > temp) {
							arr[k + gap] = arr[k];
							k -= gap;
						}
						arr[k + gap] = temp;
					}
				}

			}
		}

	}

	public static void main(String[] args) {
		int[] arr = { 1, 3, 5, 7, 9, 2, 4, 6, 8 };
		// int[] arr= {4,2,1,6,3,6,0,-5,1,1};
		shellSort(arr, arr.length);
		System.out.println(Arrays.toString(arr));
	}
}
